﻿
namespace Leetcode.N0085;
public class Solution
{
    public int MaximalRectangle(char[][] matrix)
    {
        var heights = this.GetHeights(matrix);
        var max = 0;
        for (int i = heights.Length - 1; i >= 0; i--)
        {
            if (max >= (i + 1) * heights[0].Length)
            {
                return max;
            }

            var val = this.GetMaximalRectangle(heights[i]);
            max = Math.Max(max, val);
        }
        return max;
    }

    private int GetMaximalRectangle(int[] heights)
    {
        int area = 0;
        var stack = new System.Collections.Generic.Stack<int>();

        for (int i = 0; i < heights.Length; i++)
        {
            while (stack.Count > 0 && heights[i] < heights[stack.Peek()])
            {
                var item = stack.Pop();
                var w = i - item;
                for (int j = item - 1; j >= 0; j--)
                {
                    if (heights[j] < heights[item])
                    {
                        break;
                    }
                    w++;
                }
                area = Math.Max(area, heights[item] * w);
            }
            if (stack.Count == 0 || heights[i] > heights[stack.Peek()])
            {
                stack.Push(i);
            }
        }

        while (stack.Count > 0)
        {
            var item = stack.Pop();
            var w = heights.Length - item;
            for (int j = item - 1; j >= 0; j--)
            {
                if (heights[j] >= heights[item])
                {
                    w++;
                }
                else
                {
                    break;
                }
            }
            area = Math.Max(area, heights[item] * w);
        }

        return area;
    }
    private int[][] GetHeights(char[][] matrix)
    {
        var heights = new int[matrix.Length][];
        for (int i = 0; i < matrix.Length; i++)
        {
            heights[i] = new int[matrix[i].Length];
            for (int j = 0; j < matrix[i].Length; j++)
            {
                if (matrix[i][j] != '1')
                {
                    continue;
                }
                heights[i][j] = ((i == 0) ? 0 : heights[i - 1][j]) + 1;
            }
        }
        return heights;
    }
}
